\documentclass[12pt,a4paper,oneside]{article}
\usepackage[ruled,vlined, linesnumbered]{algorithm2e}

\usepackage{graphicx}
\usepackage{paralist}

\usepackage[brazil]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{url}

%opening
\title{Relatório Trabalho Prático 2 : \\Colônia de Formigas para Otimização e Agrupamento}
\author{Ramon Pereira Lopes \\ Rangel Silva Oliveira}

\begin{document}

\maketitle

\section{Introdução}

O presente documento refere-se ao relatório do trabalho prático da disciplina de Computação Natural. O trabalho prático em questão consiste em implementar algoritmos baseados em Colônia de Formigas para um problema de otimização, especificamente o problema de resolução de labirintos, e para um problema de aprendizado de máquina, especificamente um problema de agrupamento. Para fins de implementação, a linguagem Java foi adotada, sendo que, ao final dessa etapa, experimentos foram conduzidos para avaliar tanto a sensibilidade dos parâmetros quanto o desempenho dos algoritmos implementados sobre as instâncias fornecidas.

Algoritmos de colônia de formigas é muito usado para solucionar um problema com a colaboração de vários agentes. No trabalho em questão as soluções são obtidas através do trabalho conjunto das formigas, que contribuem com uma parcela da solução. A ideia básica desses algoritmos é tentar orientar os outros agentes com uma informação obtida no cálculo de uma determinada solução, no caso das formigas o feromônio. Então, sempre é deixado um rastro de feromônio com o intuito de orientar as próximas formigas a caminharem pelas soluções. Decisões locais são tomadas de acordo com a probabilidade de se escolherem determinado passo a ser dado, portanto, a melhor solução é o caminho com maior taxa de feromônio. Todos os algoritmos apresentados neste trabalho possuem a estrutura mencionada acima.

\subsection{Otimização - Labirinto}

O problema do labirinto é bem simples. Dado um tabuleiro definido por células vazias e paredes, deve-se encontrar um caminho válido de menor custo partindo da entrada e chegando à saída do labirinto.

A solução adotada neste trabalho é simples, entretanto se mostrou muito eficaz. Dado um conjunto de formigas, o procedimento é soltá-las no ponto inicial do labirinto. Cada uma executa um passo válido no labirinto até chegar ao destino, ou até não conseguir mais executar passos válidos. Em cada iteração todas as formigas percorrem o labirinto e contribuem com uma parcela da solução, provendo diversidade dos caminhos possíveis no labirinto. Após cada iteração o feromônio é atualizado em todas as células percorridas por alguma formiga no labirinto, assim como é aplicado a taxa de evaporação do mesmo, visando escapar do mínimos locais ao passa que caminhos percorridos há mais tempo possam ser recuperados. A evaporação de feromônio é feita simplesmente multiplicando cada célula por uma constante entre 0 e 1.

Para decidir qual direção deve ser tomada dada uma posição da formiga no labirinto, é levado em consideração a quantidade de feromônio existente nas células nas quais um possível movimento seria válido. Como sempre são no máximo 4 possibilidade de movimentos, cada quantidade de feromônio na célula é somada a 0.25 com a finalidade de permitir que mesmo uma célula que não possua feromônio, ela tenha possibilidade de ser escolhida como próximo passo.

Usa-se uma roleta para escolher a nova posição da formiga, da seguinte forma:
\begin{itemize}
	\item Divide-se cada uma das 4 probabilidades pelas soma delas, gerando uma porcentagem em relação ao total;
	\item Sorteia-se um número de 0 a 1 e dependendo da distribuição nas probabilidades de escolhas, uma direção é escolhida;
	\item Mesmo que uma direção tenha maior feromônio, pode acontecer de uma célula sem feromônio ser escolhida. A ideia é que quanto maior feromônio em uma célula, mair a probabilidade de uma formiga seguir naquela direção.
\end{itemize}

A probabilidade de um movimento válido é dado pela seguinte fórmula, em que cada valor de $i$ representa uma possível movimento válido:

$$prob[i] = \frac{feromonio[i] + 0.25}{1 + \sum_{j=1}^{4}feromonio[j]}, \forall i \in \{1,2,3,4\}$$

A atualização do feromônio é feita de forma inversamente proporcional ao tamanho do caminho obtido pela formiga. Quando a formiga chega à solução apenas o tamanho do caminho é levado em consideração, no caso de uma formiga não chegar ao objetivo é somado um número grande para penalizar a escolha daquele caminho, já que não soluciona o problema. Resumindo, quanto menor o caminho, mais feromônio será deixado nas células, orientando ainda mais as próximas formigas que caminharão pelo labirinto.

$$feromonio[i] = feromonio[i] * TAXA\_EVAPORACAO,  \forall i \in Celulas\ Labirinto$$


Uma estratégia muito interessante adotada neste trabalho tem relação àquelas impossibilidade de uma formiga a dar algum passo válido. Neste caso foi adotado que a formiga cumpriu seu papel. Entretanto, uma ideia muito boa de convergência do algoritmo foi adotar que se uma formiga não consegue mais caminhar no labirinto, ela torna a célula em que ela se encontra em uma parede. Isso faz com que as formigas, ao longo das iterações, vão removendo soluções inválidas do espaço de soluções. Por exemplo, becos no labirinto são substituídos por paredes, sendo fechado com o decorrer das iterações. Somente esse procedimento realiza uma poda de soluções muito grande, promovendo uma convergência rápida.

Levando em consideração tal procedimento de gerar paredes, foi pensado em outra situação que pode levar uma formiga a entrar em \textit{loop}. Isso acontece se a próxima posição da formiga for uma já visitada por ela, o que acaba possibilitando a uma possível solução a ter ciclos, e no pior caso uma formiga pode ficar caminhos em ciclos para sempre. A solução adotada para isso é transformar em parede a célula atual em que está a formiga quando a próxima célula a ser ocupada já foi visitada por ela. Essa estratégia realiza uma série de podas que aumentam a taxa de convergência do algoritmo.

\subsection{Agrupamento}

O problema de agrupamento consiste basicamente em agrupar um conjunto de dados que apresentam características similares. Para tal fim, o algoritmo de colônia de formigas implementado baseia-se na métrica de distância euclidiana para a realização de agrupamento, como também, diferentemente de trabalhos na literatura, o espaço de trabalho adotado é uma região planar em vez de um toróide. Vale ressaltar que todos os vetores foram normalizados a fim de evitar resultados imprecisos por conta da discrepância de grandezas entre os vetores.

\begin{algorithm}
\LinesNumbered
\DontPrintSemicolon
$scatterItems()$;\;
\For{$i\leftarrow 1$ \KwTo $\#ants$}{
	$ant[i].pickFreeItem()$;\;
}

\For{$j\leftarrow 1$ \KwTo $\#iterations$}{
\For{$i\leftarrow 1$ \KwTo $\#ants$}{
	\If{$ant[i].isCarryingItem()$}{
		\If{$ant[i].drop()$}{
			$ant[i].pickFreeItem()$;\;
		}
	}\Else{
		$ant[i].pickFreeItem()$;\;
	}
	$ant[i].step()$;\;
}
}
$dropAll()$;\;
\caption{Algoritmo básico colônia de formigas\label{alg:ant}}
\end{algorithm}

A Algoritmo \ref{alg:ant} apresenta o pseudo-código do algoritmo básico da colônia de formigas. Na Linha 1, todos os itens são inseridos aleatoriamente no espaço de trabalho de duas dimensões. Nas Linhas 2 e 3, cada formiga da colônia tenta carregar probabilisticamente um item livre no espaço de trabalho. Na Linha 4, o bloco de código abaixo é executado pelo número máximo de iterações do algoritmo. Na Linha 5, o bloco de código abaixo é executado para cada formiga. Nas Linhas 6, 7 e 8, a formiga que estiver carregando um item tenta depositar probabilisticamente o item carregado no espaço de trabalho em sua posição atual, caso consiga, esta tenta carregar aleatoriamente um item livre no espaço de trabalho. Nas Linhas 9 e 10, caso a formiga não esteja carregando um item, esta tenta carregar probabilisticamente um item livre no espaço de trabalho. Na Linha 11, a formiga se movimenta no espaço de trabalho. Por fim, na Linha 12, ao término do algoritmo, cada formiga, caso esteja carregando algum item, deposita o item carregado na memória de trabalho.

\begin{algorithm}
\LinesNumbered
\DontPrintSemicolon
density = 0;\;
\For{(i,j) in Square(x,y)}{
	\If{!occupied[i][j]}{
		density += penalty;\;
	}{
		\If{i != x {\bf and} j != y}{
			density += dissimilarity[(x,y), (i,j)];\;
		}
	}
}
\textbf{return} density / (Area(Square(x,y))*penalty);\;
\caption{double dissimilarity(int x, int y)\label{alg:dis}}
\end{algorithm}

O grau de dissimilaridade é a métrica básica para as funções probabilísticas para determinar se uma formiga deve carregar ou depositar um dado item. O grau de dissimilaridade, dada a posição em que o item se encontra, é calculado pelo somatório da distância euclidiana entre o item em questão e cada item vizinho dividido pela área da vizinhança. A região de vizinhança é definida por um quadrado de lado $l$ e com centro na posição do item em questão. Durante o cálculo de dissimilaridade, caso uma posição na vizinhança esteja vazia, ocorre uma penalização a fim de garantir que itens permaneçam isolados. O pseudo-código da função de cálculo de dissimilaridade é apresentado no Algoritmo \ref{alg:dis}.

\begin{algorithm}
\LinesNumbered
\DontPrintSemicolon

	\If{$density >= 0.7$}{
		\textbf{return} 1;\;
	}\Else{
		\textbf{reutrn} density;\;
	}
\caption{double pickProbability(double density)\label{alg:pick}}
\end{algorithm}

\begin{algorithm}
\LinesNumbered
\DontPrintSemicolon

\textbf{return} 1-density;

\caption{double dropProbability(double density)\label{alg:drop}}
\end{algorithm}


Os Algoritmos \ref{alg:pick} e \ref{alg:drop} apresentam o pseudo-código dos algoritmos para cálculo das probabilidades de carregar e depositar um item, respectivamente. No Algoritmo \ref{alg:pick}, a probabilidade de um item ser carregado é diretamente proporcional ao grau de dissimilaridade, representado por \textit{density}. Por sua vez, no Algoritmo \ref{alg:drop}, a probabilidade de um item ser depositado é inversamente proporcional ao grau de dissimilaridade.

No que compete às políticas de movimentação de uma formiga no espaço de trabalho, técnicas foram adotadas para acelerar a convergência do algoritmo foram adotados. A primeira técnica adotada consiste em manter uma lista de itens livres, isto é, itens que não estão sendo carregados por outra formiga. Com base nesta lista, uma formiga que não está carregando item algum probabilisticamente carregará algum desta lista, de modo que a formiga é diretamente transportada para a posição de do item selecionado. A segunda técnica adotada consiste em manter uma memória no formigueiro com tamanho igual a 10 itens. Deste modo, uma formiga, ao carregar um novo item, tentará depositar tal item na região daquele de menor dissimilaridade dentre aqueles presentes na memória. Vale ressaltar que, inicialmente, tentou-se introduzir uma memória local para cada formiga, contudo não houve melhora significativa no algoritmo. Apesar do espaço de memória ser global, isto é, o espaço de memória pertence ao formigueiro e é acessível por todas as formigas, foi estipulado um tamanho pequeno para esse espaço.

Com base na arquitetura projetada e no algoritmo implementado, os seguintes parâmetros foram estipulados: o tamanho da vizinhança, o número de formigas, o tamanho do espaço de trabalho e o número de iterações do algoritmo. A influência de tais parâmetros no algoritmo é analisada na próxima seção.

\section{Experimentos}

\subsection{Otimização - Labirinto}

No problema do labirinto temos apenas o tamanho do caminho a ser analisado. Sendo assim, o proposto é alterar os parâmetros e ver como se comporta o algoritmo.

Para todas as instâncias o algoritmo foi executado alterando o número de formigas e o número de iterações a serem realizadas. Percebemos que a alteração do feromônio a ser depositado em cada célula não impacta nas soluções, porque na roleta apenas a porcentagem é levada em consideração. Logo, se um valor maior é depositado, o valor é distribuído pelas células, fazendo com que a porcentagem continue a mesma para todas as células possíveis de serem escolhidas.

O comportamento do algoritmo foi como esperado, diferindo apenas no critério de convergência. A convergência se mostrou muito rápida ao ponto de que quando uma formiga encontra uma solução viável ela já é a melhor encontrada no restante das iterações. Foi possível concluir que esse comportamento é devido à própria estrutura do labirinto. Não há tantos caminhos possíveis que levam à saída do algoritmo, e ainda com o fechamento de alguns becos e \textit{loops}, as formigas convergem para o melhor caminho muito rápido. Do ponto de vista prático, esse comportamento se mostrou muito bom, mas pelo lado didático acreditava-se que as soluções seriam melhoradas com as iterações, o que não aconteceu. Fato este que pode ser explicado pelo fato de as formigas desde os primeiros passos já orientarem a decisão pelo melhor sub-caminho já encontrado, já que há uma maior concentração de feromônio. Então, como a cada decisão há um ajuste do próximo passo, quando uma formiga realiza o último passo para chegar a uma solução, ela por indução, seria a melhor encontrada.

Os resultados encontrados para as instâncias são mostradas na Tabela \ref{resultados}, em que no pior caso não foi possível encontrar solução para os problemas: \newpage

\begin{table}[!h]
\begin{center}
	\begin{tabular}{|c|c|c|c|}
		\hline \hline
		\textbf{Valor} & \textbf{M1} & \textbf{M2} & \textbf{M3} \\ \hline
		\textbf{Melhor} & 942 & 3033 & 271 \\ \hline
		\textbf{Médio} & 942 & 3033 & 271 \\
		\textbf{Pior} & - & - & - \\		
		\hline \hline
	\end{tabular}
	\caption{Resultados encontradas para o algoritmo de colônia de formigas}
	\label{resultados}
	\end{center}
\end{table}

Os parâmetros de execução foram alterados para as 3 instâncias até que se achasse uma combinação que gerasse um menor tempo de processamento. Sendo assim, as execuções que encontraram solução a um menor custo computacional estão listadas abaixo:

\begin{verbatim}
--------------------------------------------------------
# Para execução do programa, execute os comandos a
# partir da pasta "pasta raiz"/bin.

# Para o labirinto M1, 200 formigas com 4 iterações
java ufmg.maze.main.Main -i ../input/M1.txt -p 200 -r 4

# Para o labirinto M2, 250 formigas com 15 iterações
java ufmg.maze.main.Main -i ../input/M2.txt -p 250 -r 15

# Para o labirinto M3, 200 formigas com 4 iterações
java ufmg.maze.main.Main -i ../input/M3.txt -p 200 -r 4
--------------------------------------------------------
\end{verbatim}

O fato de cada instância ter sido configurado com parâmetros diferentes mostra que dependendo do tamanho da entrada, os mesmos parâmetros podem não levar a uma solução viável. No caso do labirinto isso acontece pela necessidade de gerar caminhos cada vez maiores afim de chegar à saída do tabuleiro. Então, colocar um número maior de formigas e iterações, faz com que mais soluções inviáveis sejam eliminadas e o algoritmo gere caminho completos da entrada até a saída, ou seja, convirja para a solução ótima do problema.

Os gráficos a seguir apresentam o real comportamento das soluções parciais geradas pelas formigas ao longo das iterações. Em todas as instâncias analisadas o caminho gerado por cada formiga vai aumentando até que certo ponto começa diminuir, convergindo assim para a solução do problema. A semi-reta no final de cada gráfico indica a convergência do algoritmo. As oscilações apresentadas nos gráficos são devidas às tentativas de convergência para um mínimo local, mas com o decorrer das iterações os mínimos locais são eliminados.

\begin{figure}[!h]
\begin{center}
	\includegraphics[scale=0.45]{m1.png}
	\caption{Comportamento do algoritmo para o tabuleiro M1}
\end{center}
\end{figure}


\begin{figure}[!h]
\begin{center}
	\includegraphics[scale=0.45]{m2.png}
	\caption{Comportamento do algoritmo para o tabuleiro M2}
\end{center}
\end{figure}

\begin{figure}[!h]
\begin{center}
	\includegraphics[scale=0.45]{m3.png}
	\caption{Comportamento do algoritmo para o tabuleiro M3}
\end{center}
\end{figure}

\subsection{Aprendizado}

A fim de avaliar a sensibilidade dos parâmetros adotados, diversos experimentos foram realizados. Para cada configuração dos experimentos, 30 execuções foram realizadas e seus valores médios obtidos para a métrica CVBest são reportados no restante desta seção. É importante ressaltar que os experimentos foram conduzidos sobre conjunto de dados de iris.csv. Por fim, uma vez determinada a melhor combinação de parâmetros, o algoritmo implementado foi avaliado sobre todos os conjuntos de dados, isto é, os conjuntos iris.csv, moon.csv e wine.dat. No restante desta seção, o tamanho da instância será representado por $n$.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{neigh.pdf} 
  \caption{Impacto da variação do tamanho da vizinhança.}
    \label{fig:neigh}
\end{figure}


A  Figura \ref{fig:neigh} apresenta o impacto em CVBest por meio da variação do tamanho da vizinhança utilizada para o cálculo de dissimilaridade. Para tal análise, os demais parâmetros foram fixados da seguinte forma: (i) número de formigas igual a $0,5n$, (ii) tamanho do espaço de trabalho igual a $\sqrt{5n}$, (iii) número de iterações igual a $500n$. Por meio de tal gráfico, é possível constatar que o melhor resultado foi obtido com tamanho de vizinhança igual a 1, cujo valor de CVBest encontrado foi de 0,2928. Deste modo, o tamanho de vizinhança foi fixado em 1 e a sensibilidade do parâmetro relativo ao tamanho do espaço de trabalho foi a analisado.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{grid.pdf} 
  \caption{Impacto da variação do tamanho do espaço de trabalho.}
    \label{fig:grid}
\end{figure}

A Figura \ref{fig:grid} apresenta o resultado do impacto da variação do tamanho do espaço de trabalho sobre CVBest. Nesta análise, os demais parâmetros foram fixados da seguinte forma: (i) número de formigas igual a $0,5n$, (ii) tamanho da vizinhança igual a 1 (determinado na etapa anterior), (iii) número de iterações igual a $500n$. Com base no gráfico, conclui-se que o melhor valor médio de CVBest é obtido com tamanho do grid igual a $\sqrt{10n}$, cujo valor CVBest foi igual a 0,2900. Contudo, é possível notar que há uma diferença infíma de 0,0055 entre o melhor e o pior valor encontrado. De qualquer forma, o tamanho do grid foi fixado em $\sqrt{10n}$, e o parâmetro relativo à porcentagem do número de formigas em relação ao tamanho da instância foi objeto de estudo na próxima etapa.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{ants.pdf} 
  \caption{Impacto da variação do tamanho do número de formigas.}
    \label{fig:ants}
\end{figure}
   
A Figura \ref{fig:ants} apresenta a sensibilidade de CVBest em relação à variação da porcentagem do número de formigas em relação ao tamanho da instância. Para esta análise, o parâmetro relativo ao número de iterações foi mantido em $500n$, enquanto os demais parâmetros foram fixados nos valores obtidos nas análises anteriores. Por meio do gráfico, é possível concluir que o melhor resultado é alcançado com um número de formigas equivalente a $70\%$ do tamanho da instância, cujo valor de CVBest igual a 0,2280. Deste modo, o número de formigas foi fixado em $0,7n$, e a análise do último parâmetro, número de iterações, foi realizada.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{runs.pdf} 
  \caption{Impacto da variação do tamanho do número de iterações.}
    \label{fig:runs}
\end{figure}

Por fim, a Figura \ref{fig:runs} apresenta a sensibilidade de CVBest em relação à variação do número de iterações do algoritmo. Vale ressaltar que o número real de iterações é $mn$, sendo $m$ o parâmetro a ser determinado. Por meio do gráfico, conclui-se que o melhor resultado obtido, igual a 0,2208, foi alcançado quando o parâmetro $m$ foi igual a 50. Assim como a maioria dos parâmetros anteriores, o parâmetro em questão não possui um impacto significativo em CVBest.

Com base no estudo de sensibilidade realizado, os parâmetros foram fixados da seguinte forma: (i) tamanho da vizinhança igual a $1$, (ii) tamanho do espaço de trabalho igual a $\sqrt{10n}$, (iii) porcentagem de formigas igual a $0,7$ e, por fim, (iv) quantidade de iterações igual a $50n$. Com base nestes parâmetros, o desempenho do algoritmo implementado foi avaliado sobre as instâncias fornecidas.

\begin{table}[htp]
\centering
\label{tab:resultado}
\begin{tabular}{ccc}
\hline

Instância & CVBest  &  Desvio Padrão  \\
\hline
iris.csv  & 0,2310 & 0,0110 \\
moon.csv  & 0,1523 & 0,0078 \\
wine.dat & 0,4420  & 0,0110\\

\hline
\end{tabular}
\caption{Análise do algoritmo genético sobre os conjuntos de dados disponibilizados para avaliação.}
\end{table}

A Tabela 1 reporta o valor médio de CVBest obtido para as 30 execuções do algoritmo de colônia de formigas para as instâncias iris.csv, moon.csv e wine.dat. A execução do algoritmo para a instância teve como valor médio CVBest para as 30 execuções igual a 0,23 com desvio padrão de 0,0110. Para a instância moon.csv, foram encontrado valores de CVBest e desvio padrão igual a 0,1523 e 0,0078, respectivamente. Por fim, para a instância wine.dat, foi obtido um valor de CVBest igual a 0,4420 com desvio padrão de 0,0110.

\section{Conclusões}

Para o problema de agrupamento, o algoritmo de formigas implementado apresentou resultados satisfatórios para as instâncias avaliadas, apesar das dificuldades encontradas. Tais dificuldades foram contornadas definitivamente por meio da introdução do sistema de memória no algoritmo. Apesar da memória ser global, o que fere o princípio de espaço local, esta foi fixada em 10 itens e, indubitavelmente, possibilitou a obtenção dos resultados apresentados.

Já para o algoritmo proposto para o labirinto, a bio-inspiração em formigas possibilitou uma grande vantagem em relação ao algoritmo genético proposto no trabalho anterior. Observou-se que a convergência no algoritmo de formigas implementado é muito boa e quando uma formiga encontra uma solução para o problema, ou seja, uma rota completa do entrada até a saída do labirinto, os sub-caminhos já foram otimizados e a solução ótima é encontrada. Tal comportamento foi observado em todas as instâncias e a causa disso pode ser oriunda da execução das podas. Apesar de didaticamente esse comportamento não ser o esperado, na prática o algoritmo se mostrou eficiente para todas as instâncias testadas.

\bibliographystyle{plain}  % (uses file "plain.bst")
\bibliography{refs}     % expects file "myrefs.bib"
\end{document}
